package com.li.algorithm.leetcode.hot100;

public class Test7 {
    public int trap(int[] height) {
        int result = 0;
        int i = 0, j = height.length - 1;
        int maxHeight = 0;
        while (i < j) {
            //计算面积, 大于0&小于等于当前最低，减去; 大于当前最低，减去当前最低
            int area = 0;
            int left = height[i];
            int right = height[j];
            int width = j - i - 1;

            if (left == 0) {
                i++;
                continue;
            }

            if (right == 0) {
                j--;
                continue;
            }

            if (left < right) {
                int useless = 0;
                for (int k = i + 1; k < j; k++) {
                    if (height[k] > left) {
                        useless += (left - maxHeight);
                    } else if (height[k] <= left && height[k] > maxHeight){
                        useless += (height[k] - maxHeight);
                    }
                }
                area = width * left - useless - maxHeight * width;
                maxHeight = left;
                i++;
                while (height[i] < left) {
                    i++;
                }
            } else if (left > right){
                int useless = 0;
                for (int k = i + 1; k < j; k++) {
                    if (height[k] > right) {
                        useless += (right - maxHeight);
                    } else if (height[k] <= right && height[k] > maxHeight) {
                        useless += (height[k] - maxHeight);
                    }
                }
                area = width * right - useless - maxHeight * width;
                maxHeight = right;
                j--;
                while (height[j] < right) {
                    j--;
                }
            } else {
                int useless = 0;
                for (int k = i + 1; k < j; k++) {
                    if (height[k] > right) {
                        useless += (right - maxHeight);
                    } else if (height[k] <= right && height[k] > maxHeight) {
                        useless += (height[k] - maxHeight);
                    }
                }
                area = width * right - useless - maxHeight * width;
                maxHeight = right;
                i++;
                j--;
                while (height[i] < left) {
                    i++;
                }
                while (height[j] < right) {
                    j--;
                }
            }
            result += area;
            //i-1, j-1(哪个小哪个先走)如果<=前一个，再-1
        }
        return result;
    }

    public static void main(String[] args) {
        Test7 test7 = new Test7();
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(test7.trap(height));

    }
}


/**
 *     双指针答案
 *     public int trap(int[] height) {
 *         int result = 0;
 *         int i = 0, j = height.length - 1;
 *         int maxLeft = 0, maxRight = 0;
 *         while (i < j) {
 *             //计算当前格能蓄水的高度（面积）
 *             maxLeft = Math.max(maxLeft, height[i]);
 *             maxRight = Math.max(maxRight, height[j]);
 *             if (height[i] < height[j]) {
 *                 result += maxLeft - height[i];
 *                 i++;
 *             } else {
 *                 result += maxRight - height[j];
 *                 j--;
 *             }
 *         }
 *         return result;
 *     }
 *
 *
 *
 *
 */